﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;//pcur指向的是第一个节点的地址
	while (pcur)//最后的时候pcur为NULL，我们就跳出了循环
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;//next指针保存的是下个节点的地址
	}
	printf("NULL\n");
}

//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申请一个新节点
	//一个节点的大小就是结构体的大小
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;//该节点指向的下一个指针是NULL

	return node;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//不能传空值
	assert(pphead);
	//pphead---->&plist
	//对pphead进行解引用得到的就是plist
	SLTNode* newnode = SLTBuyNode(x);
 	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//尾节点-->新节点
	//phead指向的是第一个节点，我们创建一个指针pcur,pcur指向的是phead
	//我们通过pcur来寻找尾节点

	//找尾节点
		SLTNode* pcur = *pphead;
		while (pcur->next != NULL)
			//最后一个节点的next是空指针，我们对于这个循环的
		{
			pcur = pcur->next;//下一个节点的指针
		}
		//pcur的下个节点我们不让他指向的是空指针，我们让他指向的是新的节点
		pcur->next = newnode;
	}
	

	
}

//头部增加数据

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	//申请一个新节点
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;//让新的节点的指针指向之前的头节点
	*pphead = newnode;//原先是*pphead指向的头节点，现在头节点发生变化，我们让头节点变化为我们刚刚创建的新节点


}


//尾部删除数据
void SLTPopBack(SLTNode** pphead)
{
	//链表为空：不能进行删除
	assert(pphead && *pphead);//pphead就是说传上来的数据不能为空，*pphead就是说明链表不能为空
	 //处理只有一个节点的情况：要删除的就是头节点,当前指针的next为NULL
	if ((*pphead)->next == NULL)//就说明只有一个节点
		//因为箭头的优先级高，所以我们要将*pphead进行括起来
	{
		free(*pphead);//我们直接将这个节点释放
		*pphead = NULL;
	}
	else//不止一个节点
	{
		SLTNode* ptail = *pphead;//头节点   *pphead就是plist
		SLTNode* prev = NULL;//前节点为空

		//找尾节点
		while (ptail->next != NULL)
		{
			prev = ptail;//prev指向ptail的前一个节点，在经历下面的代码之后
			ptail = ptail->next;
			//我们让ptail指向下一个节点的之前，我们将现在的prev赋值为现在的ptail
			//等ptail指向下一个节点之后，那么prev就是一直指向的是前一个节点了

		}
		//假设我们有4个节点，此时的prev指向的是第三个节点，ptail指向的是最后一个节点
		//我们现在为了删除尾节点，我们将prev指向的下一个指针变为空指针
		prev->next = NULL;
		free(ptail);//我们直接将ptail这个指针进行释放，因为这个指针指向的节点就是我们要删除的尾节点
		ptail = NULL;
	}



}

//头部删除数据
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);//参数不能传空，链表不能为空

	SLTNode* next = (*pphead)->next;//将下一个节点存储起来
	free(*pphead);//直接将第一个节点进行释放

	*pphead = next;//因为我们之前将下一个节点存储起来了
	//现在我们将头节点删除了，那么新的头节点就是之前的下一个节点
	//那么我们将头节点的地址赋值上之前存储的下一个节点的地址

	//我们还能先改头结点，再进行释放
	/*
	SLTNode*del=*pphead;
	*pphead=(*pphead)->next;//将头结点改变了
	* 
	free(del);//直接将头结点释放掉
	dal=NULL;	



	*/
}


//查抄
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//返回的是一个节点的指针
{
	assert(phead);
	SLTNode* pcur = phead;//重新定义一个指针
	while (pcur!=NULL)
	{
		if (pcur->data == x)//找到了我们要找的节点了
		{
			return pcur;
		}
		
		pcur = pcur->next;
	}
	//跳出循环就说明没有我们要找的节点
	return NULL;
}


//在指定位置之前插⼊数据（传二级指针，就说明我们要将链表中数据进行改变）
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//链表是可以为空的，因为我们是插入数据不是删除数据
	assert(pos);
	
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//申请一个新的节点
		SLTNode* newnode = SLTBuyNode(x);

		//找prev:pos的前一个节点
		SLTNode* prev = *pphead;//初始定义为第一个节点
		while (prev->next != pos)//prev的下个节点不是pos我们就一直进行循环
			//直到我们的下个节点是pos,那么我们的prev就是pos的前一个节点了
			//我们的目的就达到了
		{
			prev = prev->next;
		}
		//此时已经是循环之外了，那么我们的prev已经是pos的前一个节点了 
		//我们在之前已经找到了prev和pos的位置，并且我们已经创建好了新的节点
		//现在我们将新节点放到两个节点中间，就实现了指定位置插入了
		newnode->next = pos;
		prev->next = newnode;

	}
}


//在指定位置之后插⼊数据
//我们就不用找pos前面的指针了，
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	//申请一个新的节点
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//删除pos结点    pos前一个节点和后一个节点受到影响
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//头删特殊处理
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;//创建一个指针指向头结点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;//pos前的节点指向pos的下一个节点
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	//我们需要知道三个节点，pos和pos后面要删除的节点以及删除节点后面的节点
	assert(pos&&pos->next);//pos和pos的下个节点都不能为空

	//pos  pos->next  pos->next->nxet
	SLTNode* del = pos->next;//将pos下个节点指针保存下来
	//我们需要让pos后面结点指向的要删除的节点后面的节点
	//我们要让pos节点后面是要删除的节点后面那个节点
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
	

//销毁链表
void SListDestroy(SLTNode** pphead)//传址
{
	//遍历链表找到每个节点
	//我们不能直接将第一个节点释放，我们要先将第二个节点进行保存
	//如果提前将第一个节点删除了我们就找不到后面的节点了
	assert(pphead && *pphead);//不能传空，不能传空链表

	//创建一个指针遍历链表
	SLTNode* pcur = *pphead;//先指向第一个节点
	while (pcur != NULL)
	{
		SLTNode* next = pcur->next;//将pcur指向的下个节点进行保存
		free(pcur);
		pcur = next;
		
	}
	//跳出循环的时候,pcur已经指向的是NULL
	*pphead = NULL;

}




